import java.util.HashMap;
import java.util.Map;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: Hua YY
 * Date: 2025-02-22
 * Time: 17:21
 */
class LRUCache {
    public Entry head,tail;
    public int capacity;
    public int size;
    public Map<Integer,Entry> map;


    public LRUCache(int capacity) {
        this.capacity = capacity;
        //初始化链表
        initLinkedList();
        this.size = size;
        map = new HashMap<>(capacity+2);
    }

    public int get(int key) {
        Entry node = map.get(key);
        if(node == null){
            return -1;
        }
        moveEntry(node);
        return node.value;
    }

    public void put(int key, int value) {
        Entry node = map.get(key);
        //说明有这个节点了,只需要移动这个节点即可
        if(node != null){
            node.value = value;//值不一样要更新
            moveEntry(node);
            return;
        }
        if(size == capacity){
            //删除最后一个节点，map中也要删除
            Entry lastNode = tail.pre;
            deleteNode(lastNode);
            map.remove(lastNode.key);
            size--;
        }
        //插入到头部
        Entry newNode = new Entry(key,value);
        addNode(newNode);
        map.put(key,newNode);
        size++;
    }
    private void deleteNode(Entry node){
        node.pre.next = node.next;
        node.next.pre = node.pre;
    }

    private void addNode(Entry node){
        //先连接后面的
        head.next.pre = node;
        node.next = head.next;
        //在连接head
        head.next = node;
        node.pre = head;
    }

    private void moveEntry(Entry node){
        //实现删除原节点，插入新节点到头部
        deleteNode(node);
        addNode(node);
    }

    private void initLinkedList(){
        head = new Entry();
        tail = new Entry();
        head.next = tail;
        tail.pre = head;
    }
}
class Entry{
    public Entry pre;
    public Entry next;
    public int key;
    public int value;
    public Entry(){

    }
    public Entry(int key , int value){
        this.key = key;
        this.value = value;
    }
}



/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */
public class Test20 {
}
